package LinkedList_03.Loop_LinkedList_05_Joseph;

/*
 * @Author 罗
 * @date 2020/3/12 - 9:45 下午
 *
 */

public class SingleLinkedList <T extends Child>{
    private Child first;
    private Child current;


    /**
     *
     * @param startNo   从第几个小孩开始数数
     * @param countNum  表示数几下
     * @param num       表示最初有多少个小孩在圈中，因为getSize()方法需要事先传入，否则每删除一个节点，getSize()的数量都会减小
     * @return
     */
    public Child getInterval(int startNo, int countNum,int num){

        /*辅助指针，用于指向待删除节点的前一个节点*/
        Child beforeGetting = first;
        while(true){
            if  (beforeGetting.getNextNode() == first){
//              完成遍历，beforeGetting已经指向最后一个节点
                break;
            }
            beforeGetting = beforeGetting.getNextNode();
        }
/*        将first和beforeGetting指针指向开始节点
            跳转到要取出的节点的前一个节点，跳转(m-1)次
            因为first默认已经指向了第一个节点，当要获取第一个节点的时候不用移动 0< 1-1 为false，跳过循环

 */
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNextNode();
            beforeGetting = beforeGetting.getNextNode();
        }
        Child result = null;
//      根据countNum指向要取出的小孩
        while(true){
//          beforeGetting指针和first指针都指向了同一个节点，说明只剩余一个元素
            if(first == beforeGetting){
                break;
            }
/*          first,beforeGetting同时移动 countNum - 1
                因为first指向的第一个节点
 */

            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNextNode();
                beforeGetting = beforeGetting.getNextNode();
            }

            /*
                for循环执行完之后，first指向的就是要取出的节点
            * */
//      将要取出的节点删除步骤
//          1.将要取出的节点保存
            result = first;
//          2.移动first指针到删除节点的下一个节点
            first = first.getNextNode();
//          3.将beforeGetting指针的下一个节点指向first指针，这样beforeGetting指针就还是指向first的前一个节点
            beforeGetting.setNextNode(first);

            System.out.println(result);
        }
        System.out.println("最后剩余的一个节点（还在圈中的节点）\t"+first);
        return null;
    }

/*    @Deprecated
    public Child getInterval(int m){
        if(beforeGetting == null){
*//*      经过添加操作，current指针默认指向链表的最后一个节点
            又因为该链表是环形链表，所以链表的最后一个节点就是第一个节点
 *//*
            beforeGetting = current;
        }
*//*        根据m，跳转到要取出的节点的前一个节点，跳转(m-1)次
            要站在要取出节点的上一个节点来考虑
            要取出节点i=0 开始
            但是要取出节点的上一个节点就是从 i =1开始
 *//*
        for (int i = 1; i < m; i++) {
            beforeGetting = beforeGetting.getNextNode();
        }

*//*        取出该节点的步骤
            因为是单链表，所以只能通过要取出节点的上一个节点来辅助将本节点取出
            1.先将该节点保存
 *//*
        Child result = beforeGetting.getNextNode();
//         2.再将该节点删除(将删除节点的上一个节点指向删除节点的下一个节点)
        beforeGetting.setNextNode(beforeGetting.getNextNode().getNextNode());

        if(beforeGetting.getNextNode() == beforeGetting.getNextNode().getNextNode()){
            this.first = null;
            this.current = null;
            this.beforeGetting = null;
            throw new RuntimeException("节点已经被取完");
        }
        return result;
    }*/

    public int getSize(){
        Child temp = first;
        int count = 1;
        while(true){
            temp = temp.getNextNode();
//            环型链表的结束判定有所不同
            if(temp == first){
                break;
            }
            count++;
        }
        return count;
    }

    public void addNodes(int count){
        for (int i = 0; i < count; i++) {
            addToLoop(new Child(i,"编号"+i));
        }
    }

    private void addToLoop(Child child){

        if(first == null){

            this.first = child;

        }else{
//        1.将当前指针指向新添加的节点
            current.setNextNode(child);

        }
//        2.移动当前指针到新添加的节点
        this.current = child;
//        3.这里再将链表形成一个环，如果不形成一个环，则每次遍历到末尾节点都要手动调用跳转到头节点（消耗性能，麻烦，易出错）
        this.current.setNextNode(first);
    }

    public <T> SingleLinkedList() {

    }

    public void show(){
        Child temp = first;
        while(true){
            System.out.println(temp);
            temp = temp.getNextNode();
//            环型链表的结束判定有所不同
            if(temp == first){
                break;
            }
        }
    }
}
